#include<iostream>
#include<queue>
#include<stack>

using namespace std;

struct BinaryTreeNode{
    int value;
    BinaryTreeNode * left;
    BinaryTreeNode * right;
};

BinaryTreeNode * createNode (int value){
    BinaryTreeNode * node = new BinaryTreeNode();
    node -> value = value;
    node -> left = node -> right = nullptr;
    return node;
}

void connectNode ( BinaryTreeNode * root, BinaryTreeNode * left, BinaryTreeNode * right){
    root -> left = left;
    root -> right = right;
}

// 32_02 PrintTreeInLine

void printTreeInLine( BinaryTreeNode * root ){
	if ( root == nullptr )
		return;
	queue<BinaryTreeNode *> q;
	q.push(root);
	int i = 1;
	while ( !q.empty() ){
		int tmp = 0;
		while ( i != 0 ){
			BinaryTreeNode * node = q.front();
			if ( node->left ) {
				tmp ++;
				q.push(node->left);
			}
			if ( node->right ){
				tmp ++;
				q.push(node->right);
			}

			cout << node->value << "  ";
			q.pop();
			i--;
		}
		cout << endl;
		i = i + tmp;
	}
} 

int main(void){
    BinaryTreeNode * node1 = createNode(2);
    BinaryTreeNode * node2 = createNode(3);
    BinaryTreeNode * node3 = createNode(4);
    BinaryTreeNode * node4 = createNode(5);
    BinaryTreeNode * node5 = createNode(6);
    BinaryTreeNode * node6 = createNode(7);
    BinaryTreeNode * node7 = createNode(8);
    BinaryTreeNode * node8 = createNode(9);
    BinaryTreeNode * node9 = createNode(10);
    BinaryTreeNode * node10 = createNode(11);
    BinaryTreeNode * node11 = createNode(12);

    connectNode(node1,node2,node3);
    connectNode(node2,node4,node5);
    connectNode(node3,node6,node7);
    connectNode(node4,node8,nullptr);
    connectNode(node7,node9,node10);

    // Test 1
    printTreeInLine(node1);
    return 0;
}